Image processing is a rapidly changing field which permeates a myriad of applications. Image alignment (also known as image registration) is a difficult task which must often be completed before further processing of the information contained in an image. Advances in digital computer information processing and storage technology have made the digital computer the instrument of choice when attempting to solve a complex image processing problem such as image alignment.
A survey of current image registration problems and solutions is presented by Lisa Gottesfeld Brown in "A Survey of Image Registration Techniques", ACM Computing Surveys, 24(4):326-376 (December 1992).
For purposes of this application, the term "image" is used in its broadest sense. An image may be defined as a spatial distribution of a physical property, such as radiation, electric conductivity, or reflectivity, mapped from another distribution of either the same or a different physical property. Mathematically, an image may be described as a mapping from a domain in N-dimensional space to a range in P-dimensional space, where N and P are generally small integers, although extensions to fractional dimensions may be possible as well. The range may be single-valued, such as a number, or it may require a more complex representation, such as a vector, tensor, or a color.
Thus, an image may be that which is traditionally thought of as a single two-dimensional (2D) picture, a single three-dimensional (3D) picture such as a hologram, or a series of 2D or 3D pictures taken over time so as to add a fourth dimension. An image may also be of higher dimensionality such that it is difficult or impossible to visualize in the traditional sense, but may still be manipulated mathematically and operated on by a digital computer. This generalized notion of an image encompasses various types of multi-dimensional data or data structures such as those which may be used in establishing common areas of belief between two communicating agents, or in locating some data in a database by matching with an image of the desired data.
The process of aligning two or more images, then, consists of determining the relationship between their domains. This process involves identifying a mapping function or transformation which maps points in the first domain to corresponding points in the second domain. Since the images may represent data acquired at different times, from different sensors, at different magnifications, or at different angles, what may at first seem to be a relatively simple task becomes quite arduous.
For example, consider the task of aligning images which represent data acquired from entirely different modalities, such as aligning an optical image with a similar radar image, or aligning a computed tomography (CT) scan with a similar positron emission tomography (PET) scan. Since the CT scan is normally a high-resolution grayscale image and the PET scan is a low resolution, false color image, it is likely that no point in one image is identical to any point in the other. Still, it is desirable to align features present in both images. Similarly, images of the same scene captured in different spectral channels in a remote sensing application may be quite different in appearance, even when properly aligned. Such tasks may easily become intractable for the typical human or the most powerful digital computer.
Variations among images to be aligned further complicate the alignment process. Variations may be of several types, some of which are desirable while others are undesirable. For example, undesirable variations may result from sensor distortion when acquiring the image, or noise in the image data. Desirable variations may include changes or movement of at least a portion of the subject matter of the image, such as movement due to cell growth in medical diagnostic applications, or change due to the construction of a building in aerial reconnaissance applications. Desirable variations are often enhanced by post-processing techniques after the alignment process is completed, whereas undesirable variations are preferably eliminated prior to image alignment.
A meaningful alignment of a number of images can be achieved even though most, if not all, points in one image have no obvious corresponding point in another image, as discussed above. To accommodate variations in the images to be aligned, each image may be assigned a coordinate system having an arbitrary reference point as its origin. The alignment process, then, consists of determining the mapping function or transformations among the various coordinate systems. This may be a local transformation which maps a portion of a first image to a portion of a second image, or a global transformation which maps the entire first image onto the second image.
A number of techniques have been developed for use in image alignment. Many methods utilize known landmarks or artificial reference points specifically inserted to assist in the alignment process. Knowledge of the particular class of transformation between images is employed to speed the alignment process since an exhaustive search over all possible transformations is time prohibitive. Prior knowledge of the type of transformation may also increase the confidence level of the alignment since one particular method may be better suited to detect a particular transformation.
A number of methods which relate to image alignment involve pattern recognition or template matching. These methods attempt to match a reference template or pattern to at least a portion of the subject image. To accomplish this, a match metric is used which operates as a measure of the similarity between the reference pattern and the image. A statistical method, such as determining a cross-correlation of the image and the template, is often utilized for this type of application. However, the cross-correlation must be computed for each allowable transformation of the template. The results of this exhaustive search over all possible transformations are then utilized to determine a best constant transformation across the entire image. Thus, this method has utility only in determining an aligning transformation which includes a small range of translations, rotations, and scale changes. As the number of transformations grows, this method quickly becomes computationally prohibitive. For example, to examine all combinations of 100 possible values for horizontal and vertical displacements, rotation angles, and scale shifts, would require 10.sup.8 tests.
It would be desirable, therefore, to have an alignment method which did not require an exhaustive search over all possible transformations such that a wider range of translations, rotations, and scale changes could be accommodated without becoming computationally unmanageable.
Fourier methods transform the information represented in an image from the spatial domain to the frequency domain. As a class, these methods are particularly amenable to aligning images which contain significant correlated and frequency-dependent, or narrow-band, noise. Furthermore, the Fourier methods also offer computational advantages over traditional statistical correlation methods which operate on the spatial domain representation of the images.
Phase correlation is a Fourier method which may be utilized to align images which have been translated relative to one another. Some improvements to basic phase correlation have extended its application to images which have been rotated as well as translated. More general transformations among images, however, are not suitable for detection utilizing phase correlation methods. Furthermore, relatively small local variations among images greatly reduce the likelihood of a successful alignment or match when using these methods.
Therefore, it would be desirable to have an image alignment method which would accommodate general transformations while tolerating noise present in the data of the image.
It would also be desirable to have an image alignment method capable of reliably registering two images which have small local variations.
As previously mentioned, some image alignment techniques utilize known landmarks or artificial reference points to speed the alignment process. Manual identification of a relatively stationary landmark is often used in conjunction with computerized matching. Of course, manual identification of a stationary landmark normally requires some expertise in the discipline of the underlying application for which the image processing is being performed. For example, manual identification of a stationery landmark in medical diagnostic applications would require knowledge of the location of stationary anatomical structures within the images to be aligned.
Automatic identification of common features among images may also be utilized for image alignment. This method involves searching for unique features present in the images to be aligned. Such features may include corners, line intersections, or distinctive contours. Since a global transformation is often determined based on the alignment of these features, it is important to identify a sufficient number of features to assure an alignment having a predetermined confidence level. However, an increased number of features will be more difficult to match since there may be local movement or noise in the images. Therefore, computational time increases dramatically to achieve an acceptable confidence level for the image alignment.
Automatic identification is more easily performed on artificially inserted reference points, also called fiducial markers. The fiducial markers are often identified using one of the template or pattern matching methods discussed above. Once the fiducial markers have been located in the images to be aligned, they may be used to determine a global transformation so as to align the remaining image points. This type of alignment strategy is particularly useful for determining complex transformations between images acquired through different imaging modalities since an appropriate fiducial marker may be chosen for each of the modalities. Unfortunately, this strategy is not suitable for a number of applications, such as aerial reconnaissance, due to the difficulty associated with placing a reliable fiducial marker in potentially hostile areas, including the middle of a desert or an adversarial military installation.
It would be desirable, therefore, for an image alignment method to reliably register images without the use of fiducial markers.
It would also be desirable for an image alignment method to accurately align images in which easily identifiable features are absent, or are present in such a large number that identification becomes perplexing, such as an image of a brick wall, a jungle canopy, or nuclear reactor control rods.
Point mapping techniques are often used when feature recognition is difficult or ambiguous. These techniques use a number of sophisticated search strategies which may include relaxation, cooperation or hierarchical searching to identify common points among images to be aligned or registered. Statistical methods, such as correlation, are frequently used to identify common points. Once a number of common points have been located, a global transformation is computed, similar to the methods using fiducial markers.
Any general transformation can be determined through approximation or interpolation, given a sufficient number of points. The number of points required depends on the type of transformation, the noise present in the images, local variations, and the confidence level desired, among other factors. As with previously discussed methods, these methods require a compromise between accuracy and computation time and for many applications, they are computationally prohibitive. Furthermore, utilization of statistical methods requires a relatively large number of matching points for acceptable accuracy. This makes the method unacceptable for use with images having local variations since sample points located within an area of local variation would appear as distortions when compared to those outside of the area.
It would be desirable for an image alignment method to be computationally feasible while providing accurate alignment of images related by a general transformation.
It would also be desirable for an image alignment method to properly align images having local variations.
A more recently developed image registration technique employs elastic, or "rubber-sheet" models to perform image warping. These techniques characterize the deformation of one image relative to another by the energy state associated with the elastic model. The registration transformation is determined by a minimum-energy state deformation of the elastic model which matches the image to be aligned or registered. The minimum-energy state is most often determined iteratively using standard numerical methods. A variety of methods for digital image warping may be found in the book by George Wolberg, Digital Image Warping, IEEE Computer Society Press: Los Alamitos, California (1990). These techniques are capable of determining some of the most complex transformations while managing local variations as well. However, they are computationally intensive and require significant development to determine unique elastic models for each different application.
It would be desirable, therefore, to have a single image alignment method applicable to a variety of applications and capable of aligning multiple images which are related by complex transformations without being computationally prohibitive.
The term "periodic pattern" is used here to mean a spatial pattern which is, in a region of interest, a periodic function of one or more variables.
A "periodic function" f(x) of a variable x is said to be periodic with period "a" if f(x) is non-constant and if, over the region of interest, f(x)=f(x+a).
Simple examples of periodic functions in normal rectilinear coordinates would be the familiar trigonometric sine and cosine curves and equally spaced horizontal or vertical lines, resembling venetian blinds or a picket fence.
A simple example of periodic function in circular coordinates rho and theta, where rho is the radial coordinate and theta is an angular coordinate measured from the x-axis, would be the classic "bulls-eye" target pattern of alternating white and black annular rings of equal width, measured radially.
This definition of "periodic pattern" is intended to include, as well, periodic functions of variables which are themselves transformations of the spatial coordinates, such as a bullseye pattern with rings which change width as the radius increases because the pattern is periodic in the inverse of the radius (ie 1/radius) not in the radial coordinate itself.
Periodic patterns of lines or circles are used in industry as the family of curves which are superimposed to create the moire patterns used for measuring alignment or displacement. Patterns of concentric circles, for instance, may be part of the mask for an integrated circuit.
Yet another image alignment technique exploits Moire interference patterns in the alignment process. In general, a Moire interference pattern is created by the superimposing of any two similar periodic structures which are misaligned. Since a periodic structure, such as equally spaced parallel lines or concentric circles, is required for this phenomenon to be present, the structure is normally artificially introduced into the images. This is accomplished by a variety of techniques such as printing, painting, or illumination. Successful alignment, then, involves identifying the Moire pattern, locating a single center point of the pattern (or a light spot or dark spot), and attempting to eliminate the pattern by repositioning the image to be aligned relative to the reference image.
Repositioning the image typically involves iteratively rotating the image and utilizing a statistical metric, such as correlation, to determine a match. As previously discussed, this quickly becomes computationally prohibitive. Another significant disadvantage of this technique, as with the use of fiducial markers, is that many applications are simply not amenable to the introduction of an artificial reference pattern. Even with the pattern, determination of the "best" match requires locating the peak of what may be a broad and noisy distribution.
Thus, it would be desirable to have an image alignment method which does not rely on artificial reference patterns introduced into the images to be aligned.
Moire interference patterns are often utilized in structural deformation analysis, as well. In these applications, the Moire interference fringes are desirable since they indicate the magnitude and direction of a deformation in the image relative to the reference pattern. The alignment process is actually secondary to the deformation analysis and is completed by various other alignment methods which do not use the Moire pattern. Furthermore, since the images are normally captured under controlled conditions, the alignment process is relatively simple and is often performed manually.
In a number of applications, Moire interference fringes are undesirable. These applications have prompted the development of a number of methods and apparatus to eliminate them. For example, in television broadcasting, interference between scanning lines and a similar line pattern in the original scene (or the dot pattern of a shadow-mask picture tube), results in unwanted distortions in the transmitted picture. Care is taken in the design of broadcasting and receiving equipment to eliminate such interference when possible. Color printing is another application in which Moire fringes present a problem rather than a solution. Misalignment of the various color masks often results in unwanted interference patterns in the finished product.
Most of the current image alignment methods are computationally intensive. This limits the utility of those methods in applications which require real-time processing of image data. Computer or machine vision applications requiring real-time image alignment and processing include: target identification and tracking; automated aviation take-offs, navigation, and landings; and, robotic inspection and task control, among a wide variety of other current and future applications. Thus, current image alignment methods and systems are inapplicable, or very expensive, to those applications requiring real-time image alignment.
It would be desirable, therefore, for an image alignment method to be computationally manageable so as to efficiently align multiple images for applications requiring real-time alignment of multiple images.